package com.hy;

import java.util.LinkedList;
import java.util.List;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:复原 IP 地址
 *
 * 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
 *
 * 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
 * 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或
 * 删除 s 中的任何数字。你可以按 任何 顺序返回答案
 *
 * User:Mr.Du
 * Date:2023/10/10
 * Time:22:11
 */
public class RestoreIpAddresses {

    LinkedList<String> res = new LinkedList<>();
    LinkedList<String> list = new LinkedList<>();
    public List<String> restoreIpAddresses(String s) {
        dfs(s, 0);
        return res;
    }

    /**
     * 从 s 的头部开始暴力穷举，如果发现 s[0..i] 是一个IP数字，那么我们就可以把 s 切分为 s[0..i] 和 s[i+1..]，
     * 然后我们去尝试把 s[i+1..] 去暴力切分成多个IP数字即可。
     * 这块需要借助一个List集合处理符合的IP数字，最后在结果res集合在添加
     * @param s
     * @param start
     */
    public void dfs(String s, int start){
        if(start == s.length() && list.size() == 4){
            res.add(String.join(".", list));
        }
        for(int i = start;i < s.length();i++){
            if(!isValid(s, start, i)){
                continue;
            }
            if(list.size() >= 4){
                break;
            }
            list.add(s.substring(start, i + 1));
            dfs(s, i + 1);
            list.removeLast();
        }
    }

    public boolean isValid(String s, int start, int end){
        int length = end - start + 1;

        if (length == 0 || length > 3) {
            return false;
        }
        // 如果只有一位数字，肯定是合法的
        if (length == 1) {

            return true;
        }
        // length > 1
        // 多于一位数字，但开头是 0，肯定不合法
        if (s.charAt(start) == '0') {
            return false;
        }
        // 排除了开头是 0 的情况，那么如果是两位数，怎么着都是合法的
        if (length <= 2) {
            return true;
        }
        String ss = s.substring(start, start + length);
        // 不可能大于 255
        if (Integer.valueOf(ss) > 255) {
            return false;
        } else {
            return true;
        }
    }

    public static void main(String[] args) {
        RestoreIpAddresses restoreIpAddresses = new RestoreIpAddresses();
        restoreIpAddresses.restoreIpAddresses("2552551012");
    }
}
